home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _voronoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.2 KB  |  126 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _voronoi.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/voronoi.h>
  17. #include <LEDA/segment.h>
  18. #include <LEDA/impl/delaunay_tree.h>
  19. #include <LEDA/d_array.h>
  20.  
  21.  
  22.  
  23. static d_array<point,node>* VP;
  24.  
  25. static GRAPH<point,point>*  G;
  26.  
  27. static double infi_length;
  28.  
  29. static point* XP;
  30.  
  31.  
  32. static void trace_segment(double x1, double y1, double x2, double y2, 
  33.                    double sx0, double sy0)
  34. {
  35.   point p(x1,y1);
  36.   point q(x2,y2);
  37.   point s(sx0,sy0);
  38.  
  39.   node v,w;
  40.  
  41.   if ((v = (*VP)[p]) == nil) (*VP)[p] = v = G->new_node(p);
  42.     
  43.   if ((w = (*VP)[q]) == nil) (*VP)[q] = w = G->new_node(q);
  44.  
  45.   G->new_edge(v,w,s);
  46.  
  47.  
  48. }
  49.  
  50.  
  51. static void infi_point(double x1, double y1, double x2, double y2, double* x, double* y)
  52. {
  53.   vector v(x2,y2);
  54.  
  55.   v = v.norm();
  56.  
  57.   *x = x1 + infi_length * v[0];
  58.   *y = y1 + infi_length * v[1];
  59.  
  60. }
  61.  
  62.  
  63. static int cmp_infi_pts(const point& p, const point& q)
  64. { // used to sort infi points clockwise around XP
  65.   segment  s1(*XP,p);
  66.   segment  s2(*XP,q);
  67.   return compare(s2.angle(),s1.angle());
  68. }
  69.  
  70.  
  71. void VORONOI(list<point>& site_list, double R, GRAPH<point,point>& VD)
  72. { 
  73.    if (site_list.empty()) return;
  74.  
  75.    d_array<point,node> V(nil);
  76.  
  77.    point X = site_list.head();
  78.  
  79.    VP = &V;
  80.    XP = &X;
  81.  
  82.    delaunay_tree DT;
  83.  
  84.    point p,q;
  85.    node v;
  86.  
  87.    list<point> infi_list;
  88.  
  89.    forall(p,site_list) DT.insert(p,0);
  90.  
  91.    infi_length = R;
  92.  
  93.    G = &VD;
  94.  
  95.    DT.trace_voronoi_edges(trace_segment, infi_point, 1);
  96.  
  97.  
  98.    // sort & link infinite points
  99.  
  100.    forall_nodes(v,VD) 
  101.      if (VD.outdeg(v) == 1) infi_list.append(VD[v]);
  102.  
  103.    infi_list.sort(cmp_infi_pts);
  104.  
  105.    point INFI(MAXDOUBLE,MAXDOUBLE);  
  106.  
  107.    list_item it;
  108.  
  109.    forall_items(it,infi_list)
  110.    {  node p = V[infi_list[it]];
  111.       node q = V[infi_list[infi_list.cyclic_succ(it)]];
  112.       point s = VD[VD.first_adj_edge(q)];
  113.       VD.new_edge(p,q,s); 
  114.     }
  115.  
  116.    forall_items(it,infi_list)
  117.    {  node p = V[infi_list[it]];
  118.       node q = V[infi_list[infi_list.cyclic_pred(it)]];
  119.       VD.new_edge(p,q,INFI);  
  120.     }
  121.  
  122.    V.clear();
  123.  
  124. }
  125.  
  126.